package LeetCode;

public class LC_279_PerfectSquares {

    public static void main(String[] args) {

    }

    static class Solution {
        public int numSquares(int n) {
            int[] res = new int[n + 1];
            res[0] = 0;

            for (int i = 1; i <= n; i++) {
                int minNum = Integer.MAX_VALUE;

                for (int base = 1; i - base * base >= 0; base++)
                    if (res[i - base * base] < minNum)
                        minNum = res[i - base * base];

                res[i] = minNum + 1;
            }
            return res[n];
        }

    }
}